package mine.code.question.动态规划;

import org.junit.Test;

/**
 * 在 "100 game" 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和达到或超过 100 的玩家，即为胜者。
 * <p>
 * 如果我们将游戏规则改为 “玩家不能重复使用整数” 呢？
 * <p>
 * 例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。
 * <p>
 * 给定一个整数maxChoosableInteger（整数池中可选择的最大数）和另一个整数desiredTotal（累计和），判断先出手的玩家是否能稳赢（假设两位玩家游戏时都表现最佳）？
 * <p>
 * 你可以假设maxChoosableInteger不会大于 20，desiredTotal不会大于 300。
 *
 * @author caijinnan
 */
public class _Undone我能赢吗 {


    @Test
    public void run() {
        System.out.println(canIWin(5, 10));
    }
    // 5

    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (desiredTotal > maxChoosableInteger * (maxChoosableInteger + 1) / 2) {
            return false;
        }
        int[] nums = new int[maxChoosableInteger];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = i + 1;
        }
        return win(nums, desiredTotal);
    }


    private boolean win(int[] nums, int total) {
        for (int num : nums) {
            if (num >= total) {
                return true;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            int[] newNums = new int[nums.length - 1];
            int index = 0;
            for (int j = 0; j < nums.length; j++) {
                if (i == j) {
                    continue;
                }
                newNums[index] = nums[j];
                index++;
            }
            if (!win(newNums, total - nums[i])) {
                System.out.println(nums[i]);
                return true;
            }
        }
        return false;
    }
}
